GATE CSE 2007
Q11.
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?Q12.
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?Q13.
Consider the DAG with V = {1,2,3,4,5,6}, shown below. Which of the following is NOT a topological ordering?Q15.
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that '-' denotes an empty location in the table.Q16.
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:Q17.
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?Q18.
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of the Huffman code for the letters a,b,c,d,e,f?Q19.
The control signal functions of a 4-bit binary counter are given below (where X is "don't care"): Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:Q20.
In a look-ahead carry generator, the carry generate function i G and the carry propagate function P_{i} for inputs A_{i} and B_{i} are given by: P_{i}=A_{i}\bigoplus B_{i} \; and \; G_{i}=A_{i}B_{i} The expressions for the sum bit S_{i} and the carry bit C_{i+1} of the look-ahead carry Combinational Circuit are given by: S_{i}=P_{i}\bigoplus C_{i} \; and \; C_{i+1}=G_{i}+P_{i}C_{i} Consider a two-level logic implementation of the look-ahead carry generator. Assume that all P_{i} and G_{i} are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit Combinational Circuit with and S_{3},S_{2},S_{1},S_{0} as C_{4} its outputs are respectively: